package com.julius.design.suanfa.sort;

/**
 * @author julius
 * @date 2021-10-18 上午 11:07
 * <p>
 *      各种排序算法<br/>
 *      <ol>
 *          <li>冒泡排序 bubble </li>
 *          <li>堆排序 heap </li>
 *          <li>快速排序 fast </li>
 *      </ol>
 * </p>
 */
public class SortDemo {

    /**
     * 冒泡排序（升序）
     * @param array 原始数组
     * @return 排序好的数组
     */
    public static int[] bubbleSort(int[] array){
        //临界判断
        if(array == null || array.length <= 1){
            return array;
        }

        /*
            冒泡排序就是指将大数放在最后一位,双层循环
            外层：
                排序的次数
            内层：
                需要比较的数据并交换的次数（外层循环一次，内层就少比较一次，因为已经排好了一个）

            时间复杂度 = O(外层) * O(内层) = O(数组长度) * O(数组长度) = O(N) * O(N) = O(N^2)
         */
        int length = array.length - 1;

        for(int i = 0; i < length; i++){
            //这里减去i,是因为已经排好了i个数在数组末尾
            for (int j = 0; j < length-i; j++) {
                //比较并交换
                if(array[j] > array[j+1]){
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
        return array;
    }


    public static void main(String[] args) {
        int[] array = new int[]{9, 4, 3, 1, 2};
        int[] bubbleSort = bubbleSort(array);
        System.out.println("---------------冒泡排序开始--------------");
        for (int i = 0; i < bubbleSort.length; i++) {
            System.out.print(bubbleSort[i]+" ");
        }
        System.out.println();
        System.out.println("---------------冒泡排序结束--------------");
    }




}
